
/////////////////////////////////////////////////////////////////////////////////
//
//  算法 ： 冒泡排序， 提取公用方法。
//
/////////////////////////////////////////////////////////////////////////////////

#include<iostream>

// 交换变量值
void mySwap(int &a,int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

// 打印数组
void showInfo(int arr[], int len, int seq)
{
    std::cout<< "seq "<< seq <<": ";
    for (int j = 0; j < len;j++)
    {
        std::cout << arr[j] << " " ;
    }
    std::cout << std::endl;
}

// 新增 lastChangeIndex 记录最后发生交换的位置，减少外层循环次数
void mySort(int arr[], int len=0)
{
    int m = len-1;          // 外层循环，设定 未 组大 len- 1 .
    int isChange = 1;       // 内循环是否发生交换，没有交换，已经排序好，可以直接推出。
    int lastChangeIndex = 0;// 内循环中发生交换的位置， 外部 m = lastChangeIndex ,可以跳过 排好序的部分。减少内循环，外循环的次数。
    while(m>0 && isChange)
    {
        isChange = 0;
        lastChangeIndex = 0;
        for (int j = 0; j <m;j++)
        {
            if (arr[j] > arr[j+1] )
            {
                isChange = 1;
                lastChangeIndex = j;
                mySwap(arr[j],arr[j+1]);
            }
        }
        m=lastChangeIndex;

        showInfo(arr,len,m);
        if(isChange == 0)
            break;
    }
}

int main()
{
    int arr[] = {1,2,9,5,3,8,6};
    int len = sizeof(arr) / sizeof(arr[0]);

    showInfo(arr,len,0);
    std::cout << "-------------------------------------"<<std::endl;
    mySort(arr,len);
    std::cout << "-------------------------------------"<<std::endl;
    showInfo(arr,len,0);

    return EXIT_SUCCESS;
}

